package de.pass.ch.junit;

import static org.junit.Assert.*;

import java.util.Arrays;
import java.util.Comparator;
import java.util.Random;

import org.junit.Test;

import de.pass.ch.datastr.EdgeList;
import de.pass.ch.graph.edge.CompleteEdge;

public class TestEdgeList {

	private static final Random r = new Random();

	@Test
	public void testEdgeList() {

		System.gc();

		int size = 1000000;

		int source = 0;
		int target = 0;
		int weight = 0;

		CompleteEdge e = null;

		CompleteEdge[] edges = new CompleteEdge[size];
		EdgeList list = new EdgeList();

		for (int i = 0; i < edges.length; i++) {

			source = r.nextInt(size);
			target = r.nextInt(size);
			weight = r.nextInt(500);

			e = new CompleteEdge(source, target, weight, false, true, false);

			edges[i] = e;
			list.add(e);

		}

		Comparator<CompleteEdge> comp = new CompleteEdgeComparator();

		Arrays.sort(edges, comp);
		long start = System.currentTimeMillis();
		list.sort(0, size, comp);
		System.out.println("EdgeList sort took "
				+ (System.currentTimeMillis() - start) + " ms");

		e = (CompleteEdge) list.get(0);

		for (int i = 0; i < edges.length; i++) {

			assertEquals(edges[i], e);
			e = e.getNext();

			if (i > 0) {
				if (comp.compare(edges[i - 1], edges[i]) > 0) {
					fail("Sortierung im Array stimmt nicht. -> Referenz falsch!");
				}
			}

		}

	}

	private static class CompleteEdgeComparator implements
			Comparator<CompleteEdge> {

		@Override
		public int compare(CompleteEdge e1, CompleteEdge e2) {
			if (e1.getSource() == e2.getSource()) {
				if (e1.getTarget() == e2.getTarget()) {
					return ((Integer) e1.getWeight()).compareTo((Integer) e2
							.getWeight());
				}
				return ((Integer) e1.getTarget()).compareTo((Integer) e2
						.getTarget());
			}
			return ((Integer) e1.getSource()).compareTo((Integer) e2
					.getSource());
		}

	}

}
